package offer.day8;

import java.util.Scanner;

public class No11min {
    /*
     * 面试题11：旋转数组的最小数字
     * 题目：把一个数组最开的的若干个元素搬到数组的末尾，我们称之为数组的旋转。
     * 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
     * 例如：数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1.
     *
     *
     * 思路：利用二分法，设置两个指针，第一个变量指向第一个元素，第二个变量指向最后一个元素
     * 		找到中间的数，首先和第一个变量进行对比，若是比第一个变量大，则中间元素属于前半部分数组，将第一个元素的指向移到中间位置
     * 				   然后和第二个变量进行对比，若是比第二个变量小，则中间元素属于后半部分数组，将第二个元素的指向移到中间位置
     * 		查找范围缩小一半，再进行新一轮的查找。。。
     * 		直到第一个指向前半部分数组的最后一个，第二个指向后半数组的第一个，也就是两者相邻
     * 		第二个指向的就是最小的元素
     *
     * 		其中根据旋转数组的定义还有一个特例，也就是将排序数组的前面0个元素搬到最后去，
     * 		也就是排序数组本身，这仍然是数组的一个旋转，也就是第一个数字大于最后一个数字时，直接返回第一个数字就可
     * 		若是左中右三值相等时，又该如何呢，前面的思路不能支持这种情况，
     * 		所以原来的方法不可行，
     * 		例如：1，0，1，1，1与1，1，1，0，1情况
     * 		这里我们采用顺序查找的方式进行
     *
     *
     * */
    public static void main(String[] args) {
        int[] array = new int[5];
        Scanner in = new Scanner(System.in);
        System.out.println("输如一个长度为5的数组：");
        for(int i=0;i<5;i++) {
            array[i]=in.nextInt();
        }
        System.out.println("利用旋转数组的特性，输出数组中最小的元素"+min(array));

    }

    private static int min(int[] arr){
        if(arr==null||arr.length==0) return 0;
        int left=0;
        int right=arr.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(arr[right]>arr[mid]){
                right=mid;
            }else if(arr[mid]>arr[right]){
                left=mid+1;
            }else{
                return minInOrder(arr,left,right);
            }
        }
        return arr[left];
    }

    private static int minInOrder(int[] arr,int left,int right){
        int res=arr[left];
        for(int i=left+1;i<right;i++){
            if(res>arr[i]){
                res=arr[i];
            }
        }
        return res;
    }
}
